/*
 * @lc app=leetcode.cn id=70 lang=cpp
 *
 * [70] 爬楼梯
 */

// @lc code=start
// 带备忘录的递归，节省空间和时间复杂度
#include<map>
using namespace std;
class Solution {
    map<int, int> memory; // 使用map进行记录
    int result;
public:
    int climbStairs(int n) {
        auto id = memory.find(n); // 如果找到了key为n的记录，则会返回其索引
        if (id != memory.end()) // 没找到就会返回end（）
        {
            return id->second; // 返回value
        }
        if (n == 1)
        {
            memory.insert(pair<int, int>(n, 1));
            return 1;
        }
        if (n == 2)
        {
            memory.insert(pair<int, int>(n, 2));
            return 2;
        }
        result = climbStairs(n - 1) + climbStairs(n - 2);
        memory.insert(pair<int, int>(n, result)); // 新的结果添加进map备忘录
        return result;
    }
};
/*
普通递归
if (n == 1)
{
    return 1;
}
if (n == 2)
{
    return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
*/
// @lc code=end
